home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / reuseC.me < prev    next >
Text File  |  1992-09-25  |  29KB  |  998 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .EQ
  380. delim $$
  381. gsize 12
  382. gfont R
  383. .EN
  384. .b " "
  385. .sp 1c
  386. .ta 9c
  387. .ft R
  388. .sz 12
  389. \l'17.1c'
  390. .nf
  391.  
  392.  
  393.     Reusable Software
  394.     A Collection of C-Modules
  395.  
  396.     J. Grosch
  397.  
  398.  
  399. \l'17.1c'
  400. .sp 12.5c
  401. \l'17.1c'
  402. .ft H
  403. .nf
  404.     GESELLSCHAFT F\*UR MATHEMATIK
  405.     UND DATENVERARBEITUNG MBH
  406.  
  407.     FORSCHUNGSSTELLE F\*UR
  408.     PROGRAMMSTRUKTUREN
  409.     AN DER UNIVERSIT\*AT KARLSRUHE
  410. .r
  411. \l'17.1c'
  412. .bp
  413. .oh ''Reuse - C'%'
  414. .eh ''Reuse - C'%'
  415. .nr % 0
  416. .ce 99
  417. .sz 20
  418. .b " "
  419. .sp 2
  420. Project
  421. .sp
  422. .b "Compiler Generation"
  423. .sp
  424. .sz 12
  425. \l'15c'
  426. .sp
  427. .sz 16
  428. .b "Reusable Software"
  429. .b "A Collection of C-Modules"
  430. .sp 2
  431. Josef Grosch
  432. .sp 2
  433. .sz 14
  434. Aug. 4 1992
  435. .sp
  436. .sz 12
  437. \l'15c'
  438. .sp 2
  439. Report No. 30
  440. .sp 2
  441. Copyright \(co 1992 GMD
  442. .sp 2
  443. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  444. Forschungsstelle an der Universit\*at Karlsruhe
  445. Vincenz-Prie\*snitz-Str. 1
  446. D-7500 Karlsruhe
  447. .ce 0
  448. .bp 2
  449. .uh Abstract
  450. .lp
  451. A brief description of my personal collection of reusable modules written in C is given.
  452. The modules are oriented towards compiler construction.
  453. Originally, the modules have been written in MODULA-2.
  454. .sh 1 Overview
  455. .pp
  456. The following modules exist currently (Aug. 1992):
  457. .sp 0.5
  458. .TS
  459. box center;
  460. l l.
  461. Module    Task
  462. _
  463. Memory    dynamic storage (heap) with free lists
  464. DynArray    dynamic and flexible arrays
  465. StringMem    string memory
  466. Idents    identifier table - unambiguous encoding of strings
  467. Sets    sets of scalar values (without run time checks)
  468. Positions    handling of source positions
  469. Errors    error handler for parsers and compilers
  470. Source    provides input for scanners
  471. General    miscellaneous functions
  472. System    machine dependent code
  473. Time    access to cpu-time
  474. .TE
  475. .sh 1 "Memory: dynamic storage (heap) with free lists"
  476. .sp
  477. .(b L
  478. .FT
  479. extern unsigned long MemoryUsed;
  480.                         /* Holds the total amount of memory managed by  */
  481.                         /* this module.                                 */
  482.  
  483. extern void     InitMemory      ();
  484.                         /* The memory module is initialized.            */
  485.  
  486. extern char *   Alloc           (register unsigned long ByteCount);
  487.                         /* Returns a pointer to dynamically allocated   */
  488.                         /* space of size 'ByteCount' bytes.             */
  489.  
  490. extern void     Free            (unsigned long ByteCount, char * a);
  491.                         /* The dynamically allocated space starting at  */
  492.                         /* address 'a' of size 'ByteCount' bytes is     */
  493.                         /* released.                                    */
  494. .)b
  495. .bp
  496. .sh 1 "DynArray: dynamic and flexible arrays"
  497. .pp
  498. This module provides dynamic and flexible arrays. The size of a dynamic
  499. array is determined at run time. It must be passed to a procedure to
  500. create the array. The size of such an array is also flexible, that means it
  501. can grow to arbitrary size by repeatedly calling a procedure to extend it.
  502. .sp
  503. .(b L
  504. .FT
  505. extern void MakeArray    (char * * ArrayPtr, unsigned long * ElmtCount,
  506.                           unsigned long ElmtSize);
  507.                         /* 'ArrayPtr' is set to the start address of a  */
  508.                         /* memory space to hold an array of 'ElmtCount' */
  509.                         /* elements each of size 'ElmtSize' bytes.      */
  510.  
  511. extern void ExtendArray  (char * * ArrayPtr, unsigned long * ElmtCount,
  512.                           unsigned long ElmtSize);
  513.                         /* The memory space for the array is increased  */
  514.                         /* by doubling the number of elements.          */
  515.  
  516. extern void ReleaseArray (char * * ArrayPtr, unsigned long * ElmtCount,
  517.                           unsigned long ElmtSize);
  518.                         /* The memory space for the array is released.  */
  519. .)b
  520. .lp
  521. Example:
  522. .sp 0.5
  523. .(b L
  524. .FT
  525. # define         InitialSize    100
  526. typedef ...      ElmtType;
  527. typdef  ElmtType ArrayType [100000];
  528. unsigned long    ActualSize = InitialSize;
  529. ElmtType *       ArrayPtr;
  530.  
  531. MakeArray (& ArrayPtr, & ActualSize, sizeof (ElmtType);
  532.  
  533. (* Case 1: continuously growing array *)
  534.  
  535. Index := 0;
  536. for (;;) {
  537.    Index ++;
  538.    if (Index == ActualSize)
  539.       ExtendArray (& ArrayPtr, & ActualSize, sizeof (ElmtType);
  540.  
  541.    ArrayPtr [Index] = ... ;   /* access an array element */
  542.     ... = ArrayPtr [Index];   /* "      "  "     "       */
  543. }
  544.  
  545. (* Case 2: non-continuously growing array *)
  546.  
  547. for (;;) {
  548.    Index = ... ;
  549.    while (Index >= ActualSize)
  550.       ExtendArray (& ArrayPtr, & ActualSize, size of(ElmtType);
  551.  
  552.    ArrayPtr [Index] = ... ;   /* access an array element */
  553.     ... = ArrayPtr [Index];   /* "      "  "     "       */
  554. }
  555.  
  556. ReleaseArray (& ArrayPtr, & ActualSize, sizeof (ElmtType);
  557. .)b
  558. .bp
  559. .bp
  560. .sh 1 "StringMem: string memory"
  561. .sp
  562. .(b L
  563. .FT
  564. typedef unsigned short * tStringRef;
  565.  
  566. extern  tStringRef PutString    (register char * s, register cardinal length);
  567.                         /* Stores string 's' in the string memory and   */
  568.                         /* returns a reference to the stored string.    */
  569.  
  570. extern  void    StGetString     (register tStringRef r, register char * s);
  571.                         /* Returns the string 's' from the string       */
  572.                         /* memory which is referenced by 'r'.           */
  573.  
  574. /* extern cardinal LengthSt     (register tStringRef r); */
  575. # define LengthSt(stringref) (* stringref)
  576.                         /* Returns the length of the string 's'         */
  577.                         /* which is referenced by 'r'.                  */
  578.  
  579. extern  bool    IsEqualSt       (tStringRef r, register char * s);
  580.                         /* Compares the string referenced by 'r' and    */
  581.                         /* the string 's'.                              */
  582.                         /* Returns true if both are equal.              */
  583.  
  584. extern  void    WriteString     (FILE * f, tStringRef r);
  585.                         /* The string referenced by 'r' is printed on   */
  586.                         /* the file 'f'.                                */
  587.  
  588. extern  void    WriteStringMemory ();
  589.                         /* The contents of the string memory is printed */
  590.                         /* on standard output.                          */
  591.  
  592. extern  void    InitStringMemory ();
  593.                         /* The string memory is initialized.            */
  594. .)b
  595. .bp
  596. .sh 1 "Idents: identifier table - unambiguous encoding of strings"
  597. .sp
  598. .(b L
  599. .FT
  600. typedef cardinal        tIdent;
  601.  
  602. extern  tIdent  NoIdent; /* A default identifer (empty string)          */
  603.  
  604. extern  tIdent  MakeIdent       (char * string, cardinal length);
  605.                         /* The string (of length) is mapped to a unique */
  606.                         /* identifier (an integer) which is returned.   */
  607.  
  608. extern  void    GetString       (tIdent ident, char * string);
  609.                         /* Returns the string whose identifier is 'ident'.*/
  610.  
  611. extern  tStringRef GetStringRef (tIdent ident);
  612.                         /* Returns a reference to the string identified */
  613.                         /* by 'ident'.                                  */
  614.  
  615. extern  tIdent  MaxIdent        ();
  616.                         /* Returns the currently maximal identifier.    */
  617.  
  618. extern  void    WriteIdent      (FILE * file, tIdent ident);
  619.                         /* The string encoded by the identifier 'ident' */
  620.                         /* is printed on the file.                      */
  621.  
  622. extern  void    WriteIdents     ();
  623.                         /* The contents of the identifier table is      */
  624.                         /* printed on the standard output.              */
  625.  
  626. extern  void    InitIdents      ();
  627.                         /* The identifier table is initialized.         */
  628.  
  629. extern  void    WriteHashTable  ();
  630. .)b
  631. .sh 1 "Sets: sets for scalar values"
  632. .pp
  633. The following module provides operations on sets of scalar values. The
  634. elements of the sets can be of the types int, unsigned, char, or long.
  635. The size of the sets, that is the range the elements
  636. must lie in, is not restricted. The elements can range from 0 to 'MaxSize', where
  637. 'MaxSize' is a parameter to the procedure MakeSet which dynamically allocates
  638. space for arbitrary large sets.
  639. .pp
  640. The sets are implemented as bit vectors (long []) plus some
  641. additional information to improve performance. So don't worry about speed too much because 
  642. procedures like Select, Extract, or Card are quite efficient. They don't execute a loop
  643. over all potentially existing elements always. This happens only in the worst case.
  644. .sp
  645. .(b L
  646. .FT
  647. # define BitsPerBitset          32
  648. # define LdBitsPerBitset        5
  649. # define MaskBitsPerBitset      0x0000001f
  650.  
  651. # define IsElement(Elmt, Set) ((int) ((Set)->BitsetPtr [(Elmt) >> LdBitsPerBitset] \\\\
  652.                                     << ((Elmt) & MaskBitsPerBitset)) < 0)
  653. # define Size(Set)                  ((Set)->MaxElmt)
  654. # define Select(Set)                Minimum (Set)
  655. # define IsNotEqual(Set1, Set2)     (! IsEqual (Set1, Set2))
  656. # define IsStrictSubset(Set1, Set2) (IsSubset (Set1, Set2) && \\\\
  657.                                      IsNotEqual (Set1, Set2))
  658.  
  659. typedef long    BITSET          ;
  660.  
  661. typedef struct  {
  662.       cardinal  MaxElmt         ;
  663.       cardinal  LastBitset      ;
  664.       BITSET *  BitsetPtr       ;
  665.       short     Card            ;
  666.       cardinal  FirstElmt       ;
  667.       cardinal  LastElmt        ;
  668.    } tSet;
  669.  
  670. extern void     MakeSet         (tSet * Set, cardinal MaxSize);
  671. extern void     ReleaseSet      (tSet * Set);
  672. extern void     Union           (tSet * Set1, tSet * Set2);
  673. extern void     Difference      (tSet * Set1, tSet * Set2);
  674. extern void     Intersection    (tSet * Set1, tSet * Set2);
  675. extern void     SymDiff         (tSet * Set1, tSet * Set2);
  676. extern void     Complement      (tSet * Set);
  677. extern void     Include         (tSet * Set, cardinal Elmt);
  678. extern void     Exclude         (tSet * Set, cardinal Elmt);
  679. extern cardinal Card            (tSet * Set);
  680. /* extern cardinal      Size            (tSet * Set); */
  681. extern cardinal Minimum         (tSet * Set);
  682. extern cardinal Maximum         (tSet * Set);
  683. /* extern cardinal      Select          (tSet * Set); */
  684. extern cardinal Extract         (tSet * Set);
  685. extern bool     IsSubset        (tSet * Set1, tSet * Set2);
  686. /* extern bool  IsStrictSubset  (tSet * Set1, tSet * Set2); */
  687. extern bool     IsEqual         (tSet * Set1, tSet * Set2);
  688. /* extern bool  IsNotEqual      (tSet * Set1, tSet * Set2); */
  689. /* extern bool  IsElement       (cardinal Elmt, tSet * Set); */
  690. extern bool     IsEmpty         (tSet * Set);
  691. extern bool     Forall          (tSet * Set, bool (* Proc) ());
  692. extern bool     Exists          (tSet * Set, bool (* Proc) ());
  693. extern bool     Exists1         (tSet * Set, bool (* Proc) ());
  694. extern void     Assign          (tSet * Set1, tSet * Set2);
  695. extern void     AssignElmt      (tSet * Set, cardinal Elmt);
  696. extern void     AssignEmpty     (tSet * Set);
  697. extern void     ForallDo        (tSet * Set, void (* Proc) ());
  698. extern void     ReadSet         (FILE * File, tSet * Set);
  699. extern void     WriteSet        (FILE * File, tSet * Set);
  700. extern void     InitSets        ();
  701. .)b
  702. .pp
  703. Two parameters of type 'tSet' passed to one of the above procedures must have
  704. the same size, that is they must have been created by passing the same
  705. value 'MaxSize' to the procedure 'MakeSet'. A parameter representing an
  706. element (of type CARDINAL or equivalent) passed to one of the above
  707. procedures must have a value between 0 and 'MaxSize' of the
  708. involved set which is the other parameter passed. If the two conditions
  709. above, which can be verified at
  710. programming time, don't hold then strange things will happen,
  711. because there are no checks at run time, of course.
  712. .(b L
  713. .lp 
  714. The following table explains the semantics of the set operations:
  715. .sp 0.5
  716. .TS
  717. ;
  718. l l.
  719. Procedure    Semantics
  720. _
  721. MakeSet    allocates space for a set to hold elements
  722.      ranging from 0 to 'MaxSize'.
  723. ReleaseSet    releases the space taken by a set.
  724. Union    Set1 := Set1 \(cu Set2
  725. Difference    Set1 := Set1 - Set2
  726. Intersection    Set1 := Set1 \(ca Set2
  727. SymDiff    Set1 := Set1 \(xo Set2     (* corresponds to exclusive or *)
  728. Complement    Set := { 0 .. MaxSize } - Set
  729. Include    Set := Set \(cu { Elmt }
  730. Exclude    Set := Set - { Elmt }
  731. Card    returns number of elements in Set
  732. Size    returns 'MaxSize' given at creation time
  733. Minimum    returns smallest element x from Set
  734. Maximum    returns largest element x from Set
  735. Select    returns arbitrary element x from Set
  736. Extract    returns arbitrary element x from Set and removes it from Set
  737. IsSubset    Set1 \(ib Set2
  738. IsStrictSubset    Set1 \(sb Set2
  739. IsEqual    Set1 \(eq Set2
  740. IsNotEqual    Set1 \(!= Set2
  741. IsElement    Elmt \(mo Set
  742. IsEmpty    Set \(eq \(O/
  743. Forall    \(fa e \(mo Set : Proc (e)   /* predicate Proc must hold for all elements */
  744. Exists    \(te e \(mo Set : Proc (e)   /* predicate Proc must hold for at least 1 element */
  745. Exists1    | { e \(mo Set : Proc (e) } | \(eq 1
  746. Assign    Set1 := Set2
  747. AssignElmt    Set1 := { Elmt }
  748. AssignEmpty    Set1 := \(O/
  749. ForallDo    FOR e := 0 TO MaxSize DO
  750.           IF e \(mo Set THEN Proc (e); END;
  751.      END;
  752. ReadSet    read external representation of a set from file 'tFile'.
  753. WriteSet    write external representation of a set to file 'tFile'.
  754.      Example output: { 0 5 6 123}
  755. .TE
  756. .)b
  757. .bp
  758. .sh 1 "Positions: handling of source positions"
  759. .pp
  760. A simple representation of the position of tokens in a source file consisting of a line
  761. and a column field. This module should be copied and tailored to the user's needs, if
  762. necessary. Modifications may be necessary if the type SHORTCARD is to small to count
  763. the lines or an extra field is needed to describe the source file.
  764. .sp
  765. .(b L
  766. .FT
  767. typedef struct { unsigned short Line, Column; } tPosition;
  768.  
  769. extern tPosition NoPosition;
  770.                         /* A default position (0, 0).                   */
  771.  
  772. extern int  Compare       (tPosition Position1, tPosition Position2);
  773.                         /* Returns -1 if Position1 < Position2.         */
  774.                         /* Returns  0 if Position1 = Position2.         */
  775.                         /* Returns  1 if Position1 > Position2.         */
  776.  
  777. extern void WritePosition (FILE * File, tPosition Position);
  778.                         /* The 'Position' is printed on the 'File'.     */
  779. .)b
  780. .sh 1 "Errors: error handler for parsers and compilers"
  781. .pp
  782. This module is needed by parsers generated with the parser generators
  783. .i lalr
  784. or
  785. .i ell .
  786. It can also b used to report error messages found during scanning or semantic analysis.
  787. Note: This module has to be copied, too, if the module
  788. .i Positions
  789. is copied and modified because it depends upon this module.
  790. .sp
  791. .(l L
  792. .FT
  793. # define xxNoText               0
  794. # define xxSyntaxError          1       /* error codes          */
  795. # define xxExpectedTokens       2
  796. # define xxRestartPoint         3
  797. # define xxTokenInserted        4
  798. # define xxTooManyErrors        5
  799.  
  800. # define xxFatal                1       /* error classes        */
  801. # define xxRestriction          2
  802. # define xxError                3
  803. # define xxWarning              4
  804. # define xxRepair               5
  805. # define xxNote                 6
  806. # define xxInformation          7
  807.  
  808. # define xxNone                 0
  809. # define xxInteger              1       /* info classes         */
  810. # define xxShort                2
  811. # define xxLong                 3
  812. # define xxReal                 4
  813. # define xxBoolean              5
  814. # define xxCharacter            6
  815. # define xxString               7
  816. # define xxSet                  8
  817. # define xxIdent                9
  818. .bp
  819. extern void (* Errors_Exit) ();
  820.                         /* Refers to a procedure that specifies         */
  821.                         /* what to do if 'ErrorClass' = Fatal.          */
  822.                         /* Default: terminate program execution.        */
  823.  
  824. extern void StoreMessages (bool Store);
  825.                         /* Messages are stored if 'Store' = TRUE        */
  826.                         /* for printing with the routine 'WriteMessages'*/
  827.                         /* otherwise they are printed immediately.      */
  828.                         /* If 'Store'=TRUE the message store is cleared.*/
  829.  
  830. extern void ErrorMessage  (int ErrorCode, int ErrorClass, tPosition Position);
  831.                         /* Report a message represented by an integer   */
  832.                         /* 'ErrorCode' and classified by 'ErrorClass'.  */
  833.  
  834. extern void ErrorMessageI (int ErrorCode, int ErrorClass, tPosition Position,
  835.                            int InfoClass, char * Info);
  836.                         /* Like the previous routine with additional    */
  837.                         /* information of type 'InfoClass' at the       */
  838.                         /* address 'Info'.                              */
  839.  
  840. extern void Message       (char * ErrorText, int ErrorClass, tPosition Position);
  841.                         /* Report a message represented by a string     */
  842.                         /* 'ErrorText' and classified by 'ErrorClass'.  */
  843.  
  844. extern void MessageI      (char * ErrorText, int ErrorClass, tPosition Position,
  845.                            int InfoClass, char * Info);
  846.                         /* Like the previous routine with additional    */
  847.                         /* information of type 'InfoClass' at the       */
  848.                         /* address 'Info'.                              */
  849.  
  850. extern void WriteMessages (FILE * File);
  851.                         /* The stored messages are sorted by their      */
  852.                         /* source position and printed on 'File'.       */
  853. .)l
  854. .bp
  855. .sh 1 "Source: provides input for scanners"
  856. .pp
  857. This module is needed by scanners generated with the scanner generator
  858. .i rex .
  859. .sp
  860. .(b L
  861. .FT
  862. extern int  BeginSource  (char * FileName);
  863.  
  864.    /*
  865.       BeginSource is called from the scanner to open files.
  866.       If not called input is read form standard input.
  867.    */
  868.  
  869. extern int  GetLine      (int File, char * Buffer, int Size);
  870.  
  871.    /*
  872.       GetLine is called to fill a buffer starting at address 'Buffer'
  873.       with a block of maximal 'Size' characters. Lines are terminated
  874.       by newline characters (ASCII = 0xa). GetLine returns the number
  875.       of characters transferred. Reasonable block sizes are between 128
  876.       and 2048 or the length of a line. Smaller block sizes -
  877.       especially block size 1 - will drastically slow down the scanner.
  878.    */
  879.  
  880. extern void CloseSource  (int File);
  881.  
  882.    /*
  883.       CloseSource is called from the scanner at end of file respectively
  884.       at end of input. It can be used to close files.
  885.    */
  886. .)b
  887. .sh 1 "General: miscellaneous functions"
  888. .sp
  889. .(b L
  890. .FT
  891. # define Min(a,b) ((a <= b) ? a : b)
  892.                         /* Returns the minimum of 'a' and 'b'.          */
  893. # define Max(a,b) ((a >= b) ? a : b)
  894.                         /* Returns the maximum of 'a' and 'b'.          */
  895.  
  896. extern cardinal         Log2 (register unsigned long x);
  897.                         /* Returns the logarithm to the base 2 of 'x'.  */
  898. extern unsigned long    Exp2 (register cardinal x);
  899.                         /* Returns 2 to the power of 'x'.               */
  900. .)b
  901. .bp
  902. .sh 1 "System: machine dependent code"
  903. .pp
  904. This module provides a few machine dependent operations.
  905. .sp
  906. .(l L
  907. .FT
  908. /* interface for machine dependencies */
  909.  
  910. # define tFile int
  911.  
  912. /* binary IO */
  913.  
  914. extern tFile    OpenInput       (char * FileName);
  915.                         /* Opens the file whose name is given by the    */
  916.                         /* string parameter 'FileName' for input.       */
  917.                         /* Returns an integer file descriptor.          */
  918.  
  919. extern tFile    OpenOutput      (char * FileName);
  920.                         /* Opens the file whose name is given by the    */
  921.                         /* string parameter 'FileName' for output.      */
  922.                         /* Returns an integer file descriptor.          */
  923.  
  924. extern int      Read            (tFile File, char * Buffer, int Size);
  925.                         /* Reads 'Size' bytes from file 'tFile' and     */
  926.                         /* stores them in a buffer starting at address  */
  927.                         /* 'Buffer'.                                    */
  928.                         /* Returns the number of bytes actually read.   */
  929.  
  930. extern int      Write           (tFile File, char * Buffer, int Size);
  931.                         /* Writes 'Size' bytes from a buffer starting   */
  932.                         /* at address 'Buffer' to file 'tFile'.         */
  933.                         /* Returns the number of bytes actually written.*/
  934.  
  935. extern void     Close           (tFile File);
  936.                         /* Closes file 'tFile'.                         */
  937.  
  938. extern bool IsCharacterSpecial  (tFile File);
  939.                         /* Returns TRUE when file 'tFile' is connected  */
  940.                         /* to a character device like a terminal.       */
  941.  
  942.  
  943. /* calls other than IO */
  944.  
  945. extern char *   SysAlloc        (long ByteCount);
  946.                         /* Returns a pointer to dynamically allocated   */
  947.                         /* memory space of size 'ByteCount' bytes.      */
  948.                         /* Returns NIL if space is exhausted.           */
  949.  
  950. extern long     Time            ();
  951.                         /* Returns consumed cpu-time in milliseconds.   */
  952.  
  953. extern int      GetArgCount     ();
  954.                         /* Returns number of arguments.                 */
  955.  
  956. extern void     GetArgument     (int ArgNum, char * Argument);
  957.                         /* Stores a string-valued argument whose index  */
  958.                         /* is 'ArgNum' in the memory area 'Argument'.   */
  959.  
  960. extern void     PutArgs         (int Argc, char * * Argv);
  961.                         /* Dummy procedure that passes the values       */
  962.                         /* 'argc' and 'argv' from Modula-2 to C.        */
  963.  
  964. extern int      ErrNum          ();
  965.                         /* Returns the current system error code.       */
  966.  
  967. extern int      System          (char * String);
  968.                         /* Executes an operating system command given   */
  969.                         /* as the string 'String'. Returns an exit or   */
  970.                         /* return code.                                 */
  971.  
  972. extern void     Exit            (int Status);
  973.                         /* Terminates program execution and passes the  */
  974.                         /* value 'Status' to the operating system.      */
  975.  
  976. extern void     BEGIN_System    ();
  977.                         /* Dummy procedure with empty body.             */
  978. .)l
  979. .sh 1 "Time: access to cpu-time"
  980. .sp
  981. .(b L
  982. .FT
  983. extern int      StepTime        ();
  984.                         /* Returns the sum of user time and system time */
  985.                         /* since the last call to 'StepTime' in milli-  */
  986.                         /* seconds.                                     */
  987.  
  988. extern void     WriteStepTime   (char * string);
  989.                         /* Writes a line consisting of the string       */
  990.                         /* 'string' and the value obtained from a call  */
  991.                         /* to 'StepTime' on standard output.            */
  992. .)b
  993. .bp 1
  994. .lp
  995. .b Contents
  996. .sp
  997. .xp
  998.